#ifndef DYNAMICPLANNING_H
#define DYNAMICPLANNING_H
#include <iostream>
#include <vector>
#include <string>
#include <math.h>

class DynamicPlanning {
    public:
    // 爬楼梯动态规划常规版
    int ClimbStairsDP(int n);
    // 爬楼梯动态规划空间优化版
    int ClimbStairsDPComp(int n);
    // 最小代价爬楼梯动态规划常规版
    int minCostClimbStairsDP(std::vector<int>& cost);
    // 最小路径和-暴力搜索
    int minPathSumDFS(std::vector<std::vector<int>>& grid,int i,int j);
    // 最小路径和-记忆化搜索
    int minPathSumDFSMem(std::vector<std::vector<int>>& grid,std::vector<std::vector<int>>& mem,int i,int j);
    // 最小路径和-动态规划
    int minPathSumDP(std::vector<std::vector<int>>& grid);
    // 最小路径和-动态规划-空间优化
    int minPathSumDPComp(std::vector<std::vector<int>>& grid);
    // 0-1背包-暴力搜索
    int knapackDFS(std::vector<int> &wgt,std::vector<int>& val,int i,int c);
    // 0-1背包-记忆化搜索
    int knapackDFSMem(std::vector<int> &wgt,std::vector<int>& val,std::vector<std::vector<int>>& mem,int i,int c);
    // 0-1背包-动态规划
    int knapackDP(std::vector<int> &wgt,std::vector<int>& val,int cap);
    // 0-1背包-动态规划-空间优化
    int knapackDPComp(std::vector<int> &wgt,std::vector<int>& val,int cap);

    // 完全背包-动态规划
    int unboundedknapackDP(std::vector<int> &wgt,std::vector<int>& val,int cap);
    // 完全背包-动态规划-空间优化
    int unboundedknapackDPComp(std::vector<int> &wgt,std::vector<int>& val,int cap);

    // 完全背包问题特例-零钱兑换-动态规划
    int CoinsChangeDP(std::vector<int>& coins,int amt);

    // 完全背包问题特例-零钱兑换-空间优化
    int CoinsChangeDPComp(std::vector<int>& coins,int amt);
    // 完全背包问题特例-零钱兑换II-动态规划
    int CoinsChangeIIDP(std::vector<int>& coins,int amt);
    // 完全背包问题特例-零钱兑换II-空间优化
    int CoinsChangeIIDPComp(std::vector<int>& coins,int amt);

    // 编辑距离问题-动态规划
    int EditDiatance(std::string& s,std::string& t);

    // 编辑距离问题-动态规划-空间优化
    int EditDiatanceComp(std::string& s,std::string& t);

    private:

};

#endif
